{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Distinct Islands II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #hash-table #hash-function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #哈希表 #哈希函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numDistinctIslands2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同岛屿的数量 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个&nbsp;<code>m x n</code>&nbsp;二进制数组表示的网格&nbsp;<code>grid</code> ，一个岛屿由 <strong>四连通</strong> （上、下、左、右四个方向）的 <code>1</code> 组成（代表陆地）。你可以认为网格的四周被海水包围。</p>\n",
    "\n",
    "<p>如果两个岛屿的形状相同，或者通过旋转（顺时针旋转 90°，180°，270°）、翻转（左右翻转、上下翻转）后形状相同，那么就认为这两个岛屿是相同的。</p>\n",
    "\n",
    "<p>返回 <em>这个网格中形状 <strong>不同</strong> 的岛屿的数量&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/05/01/distinctisland2-1-grid.jpg\" style=\"height: 162px; width: 200px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong> 这两个是相同的岛屿。因为我们通过 180° 旋转第一个岛屿，两个岛屿的形状相同。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/05/01/distinctisland1-1-grid.jpg\" style=\"height: 162px; width: 200px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]\n",
    "<strong>输出:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;不是&nbsp;<code>0</code>&nbsp;就是&nbsp;<code>1</code>.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-distinct-islands-ii](https://leetcode.cn/problems/number-of-distinct-islands-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-distinct-islands-ii](https://leetcode.cn/problems/number-of-distinct-islands-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]', '[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        shape=set()\n",
    "\n",
    "        def check(arr):\n",
    "            n=len(arr)\n",
    "            dis=0\n",
    "            for i in range(n-1):\n",
    "                for j in range(i+1,n):\n",
    "                    x,y=arr[i]\n",
    "                    x1,y1=arr[j]\n",
    "                    dis=dis+((x-x1)**2+(y-y1)**2)**(0.5)\n",
    "            f=0\n",
    "            for x in shape:\n",
    "                if abs(x-dis)<=0.00001:\n",
    "                    f=1\n",
    "                    break\n",
    "            if f==0:\n",
    "                shape.add(dis)\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    tmp=[]\n",
    "                    grid[i][j]=0\n",
    "                    stack=collections.deque()\n",
    "                    stack.append([i,j])\n",
    "                    while stack:\n",
    "                        x,y=stack.popleft()\n",
    "                        tmp.append([x,y])\n",
    "                        for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                            if 0<=x1<m and 0<=y1<n and grid[x1][y1]==1:\n",
    "                                grid[x1][y1]=0\n",
    "                                stack.append([x1,y1])\n",
    "                    check(tmp)\n",
    "        return len(shape)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        s=set()\n",
    "        ans=0\n",
    "        ls=[]\n",
    "        d=[[1,0],[0,1],[0,-1],[-1,0]]\n",
    "        def dfs(x,y):\n",
    "            if x<0 or y<0 or x>=m or y>=n:\n",
    "                return \n",
    "            if grid[x][y]==0:\n",
    "                return\n",
    "            grid[x][y]=0\n",
    "            ls.append((x,y)) \n",
    "            for dx,dy in d:\n",
    "                dfs(x+dx,y+dy)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    ls=[]\n",
    "                    dfs(i,j)\n",
    "                    now=0\n",
    "                    for a,b in ls:\n",
    "                        for aa,bb in ls:\n",
    "                            now+=((a-aa)**2+(b-bb)**2)**0.5\n",
    "                    now=round(now,5)\n",
    "                    if now in s:\n",
    "                        continue \n",
    "                    else:\n",
    "                        ans+=1\n",
    "                        s.add(now)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n, dc, alhas, res = len(grid), len(grid[0]), {}, set(), 0\n",
    "        def find(x):\n",
    "            if x not in dc: dc[x] = x\n",
    "            elif dc[x] != x: dc[x] = find(dc[x])\n",
    "            return dc[x]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    key = (i,j)\n",
    "                    dc[key] = key\n",
    "                    if i > 0 and grid[i-1][j]:\n",
    "                        dc[key] = find((i-1,j))\n",
    "                        if j > 0 and grid[i][j-1]:\n",
    "                            dc[find((i,j-1))] = dc[key]\n",
    "                    if j > 0 and grid[i][j-1]:\n",
    "                        dc[key] = find((i,j-1))\n",
    "        ss = defaultdict(list)\n",
    "        for i,v in dc.items():\n",
    "            ss[find(v)].append(i)\n",
    "        for lis in ss.values():\n",
    "            x0, y0 = lis[0]\n",
    "            x1, y1 = lis[0]\n",
    "            for i,j in lis:\n",
    "                x0, y0, x1, y1 = min(x0,i), min(y0,j), max(x1,i), max(y1,j)\n",
    "            POS = [[0,0,1,0,0,1],[0,x1-x0,0,1,-1,0],[x1-x0,y1-y0,-1,0,0,-1],[y1-y0,0,0,-1,1,0],[0,0,0,1,1,0],[0,y1-y0,1,0,0,-1],[y1-y0,x1-x0,0,-1,-1,0],[x1-x0,0,-1,0,0,1]]\n",
    "            has = [[] for _ in range(8)]\n",
    "            # print(x1,y1)\n",
    "            for i,j in lis:\n",
    "                ni, nj = i - x0, j - y0\n",
    "                for k in range(8):\n",
    "                    x, y, dxx, dxy, dyx, dyy = POS[k]\n",
    "                    has[k].append((x+ni*dxx+nj*dxy,y+ni*dyx+nj*dyy))\n",
    "            # print(has)\n",
    "            if tuple(has[0]) not in alhas:\n",
    "                res += 1\n",
    "                for i in has:\n",
    "                    alhas.add(tuple(sorted(i)))\n",
    "            # print(alhas)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        def dfs(r,c):\n",
    "            if 0<=r<m and 0<=c<n and grid[r][c]==1:\n",
    "                # flooding it to avoid visit it again\n",
    "                grid[r][c]=0\n",
    "                shape.add(complex(r,c))\n",
    "                dfs(r+1,c)\n",
    "                dfs(r-1,c)\n",
    "                dfs(r,c-1)\n",
    "                dfs(r,c+1)\n",
    "        def standardize(shape:set):\n",
    "            # trans表示对一个形状list进行归一化处理，得到一个sorted list，里面是每个点的相对矩形左上角的坐标，是一个归一化的过程\n",
    "            def trans(shape:set):\n",
    "                tl=complex(min(z.real for z in shape),min(z.imag for z in shape))\n",
    "                return sorted(str(z-tl) for z in shape)\n",
    "                \n",
    "            ans=[]\n",
    "            for k in range(4):\n",
    "                # (a+bj)*j表示一次顺时针旋转\n",
    "                # (a+bj)->(-b+aj)->(-a-bj)->(b-aj)\n",
    "                ans=max(ans,trans([z*(1j)**k for z in shape]))\n",
    "                # 由于所有的旋转过后的点的x-y对称也要考虑，因此还有其他四个点\n",
    "                # (b+aj)->(-a+bj)->(-b-aj)->(a-bj)\n",
    "                ans=max(ans,trans([complex(z.imag,z.real)*(1j)**k for z in shape]))\n",
    "            return tuple(ans)\n",
    "\n",
    "        shapes=set()\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                shape=set()\n",
    "                # 结果会被放进shape\n",
    "                dfs(r,c)\n",
    "                # 然后对这个结果产生8个不同的变换，选出最大的变换\n",
    "                if shape:\n",
    "                    shapes.add(standardize(shape))\n",
    "        return len(shapes)\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != 1:\n",
    "                return \n",
    "            shape.append(complex(i, j))\n",
    "            grid[i][j] = 0\n",
    "            dfs(i - 1, j)\n",
    "            dfs(i, j - 1)\n",
    "            dfs(i + 1, j)\n",
    "            dfs(i, j + 1)\n",
    "        def standardize(shape):\n",
    "            def transform(shape):\n",
    "                s = complex(min(s.real for s in shape), min(s.imag for s in shape))\n",
    "                return sorted(str(z - s) for z in shape)\n",
    "            res = []\n",
    "            for i in range(4):\n",
    "                res = max(res, transform([s * (1j) ** i for s in shape]))\n",
    "                res = max(res, transform([complex(s.imag, s.real) * (1j) ** i for s in shape]))\n",
    "            return tuple(res)\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    shape = []\n",
    "                    dfs(i, j)\n",
    "                    res.add(standardize(shape))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        pos=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        # 遍历连通区域\n",
    "        def dfs(x,y):\n",
    "            vis.add((x,y))\n",
    "            grid[x][y]=0\n",
    "            for dx,dy in pos:\n",
    "                xx,yy=x+dx,y+dy\n",
    "                if 0<=xx<m and 0<=yy<n and grid[xx][yy]==1:\n",
    "                    dfs(xx,yy)\n",
    "        # 计算哈希值\n",
    "        def hashcode():\n",
    "            s=0\n",
    "            arr=list(vis)\n",
    "            k=len(arr)\n",
    "            dist=0\n",
    "            for i in range(k):\n",
    "                x,y=arr[i]\n",
    "                for j in range(i+1,k):\n",
    "                    a,b=arr[j]\n",
    "                    dist+=((x-a)**2+(y-b)**2)**0.5\n",
    "            for ca in candi:\n",
    "                if abs(dist-ca)<1e-5:\n",
    "                    break\n",
    "            else:\n",
    "                candi.add(dist)\n",
    "\n",
    "        vis=set()\n",
    "        candi=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    dfs(i,j)\n",
    "                    hashcode()\n",
    "                    vis.clear()\n",
    "        \n",
    "        return len(candi)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != 1:\n",
    "                return \n",
    "            shape.append(complex(i, j))\n",
    "            grid[i][j] = 0\n",
    "            dfs(i - 1, j)\n",
    "            dfs(i, j - 1)\n",
    "            dfs(i + 1, j)\n",
    "            dfs(i, j + 1)\n",
    "        def standardize(shape):\n",
    "            def transform(shape):\n",
    "                s = complex(min(s.real for s in shape), min(s.imag for s in shape))\n",
    "                return sorted(str(z - s) for z in shape)\n",
    "            res = []\n",
    "            for i in range(4):\n",
    "                res = max(res, transform([s * (1j) ** i for s in shape]))\n",
    "                res = max(res, transform([complex(s.imag, s.real) * (1j) ** i for s in shape]))\n",
    "            return tuple(res)\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    shape = []\n",
    "                    dfs(i, j)\n",
    "                    res.add(standardize(shape))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pos = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        def dfs(i, j):\n",
    "            vis.add((i, j))\n",
    "            grid[i][j] = 0\n",
    "            for dx, dy in pos:\n",
    "                x, y = i + dx, j + dy \n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:\n",
    "                    dfs(x, y)\n",
    "        \n",
    "        def check():\n",
    "            s = 0\n",
    "            nums = list(vis)\n",
    "            n = len(nums)\n",
    "            d = 0\n",
    "            for i in range(n):\n",
    "                x, y = nums[i]\n",
    "                for j in range(i + 1, n):\n",
    "                    a, b = nums[j]\n",
    "                    d += ((x - a) ** 2 + (y - b) ** 2) ** 0.5\n",
    "            \n",
    "            for x in res:\n",
    "                if abs(d - x) < 1e-5:\n",
    "                    break\n",
    "            else:\n",
    "                res.add(d)\n",
    "        \n",
    "        vis = set()\n",
    "        res = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    dfs(i, j)\n",
    "                    check()\n",
    "                    vis.clear()\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        islands = []  # keep all points of islands in a row\n",
    "        def find_next(r, c, idx):  # DFS to find the island\n",
    "            grid[r][c] = 0\n",
    "            islands[idx].append((r,c))\n",
    "            for i, j in [(-1,0), (1,0), (0,-1), (0,1)]:\n",
    "                if 0 <= r+i < len(grid) and 0 <= c+j < len(grid[0]) and grid[r+i][c+j] == 1:\n",
    "                    find_next(r+i, c+j, idx)\n",
    "\n",
    "        hashed_cache = set()\n",
    "        def add_hash(idx):  # add to hash_cache if uniqe\n",
    "            sig = []\n",
    "            # total 8 ways to reshape\n",
    "            for i, j in [(1,1), (1,-1), (-1,1), (-1,-1)]: \n",
    "                for s in (True, False):\n",
    "                    mnx, mny = inf, inf\n",
    "                    sig = []\n",
    "                    for p in islands[idx]:\n",
    "                        mnx = min(mnx, p[0]*i if s else p[1]*i)\n",
    "                        mny = min(mny, p[1]*j if s else p[0]*j)\n",
    "                    for p in islands[idx]:\n",
    "                        sig.append(((p[0]*i if s else p[1]*i) - mnx, (p[1]*j if s else p[0]*j) - mny))\n",
    "                    sig.sort()  # to build hash signature\n",
    "                    if tuple(sig) in hashed_cache:  # has a shape already in\n",
    "                        return  \n",
    "            hashed_cache.add(tuple(sig))  # no shape found, unique, add\n",
    "        \n",
    "        # find islands\n",
    "        for r in range(len(grid)):\n",
    "            for c in range(len(grid[0])):\n",
    "                if grid[r][c] == 1:\n",
    "                    islands.append([])\n",
    "                    find_next(r, c, len(islands)-1)\n",
    "\n",
    "        # build unique hash\n",
    "        for i in range(len(islands)):\n",
    "            add_hash(i)\n",
    "            \n",
    "        return len(hashed_cache)\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        islands = []\n",
    "        def find_next(r, c, idx):\n",
    "            grid[r][c] = 0\n",
    "            islands[idx].append((r,c))\n",
    "            for i, j in [(-1,0), (1,0), (0,-1), (0,1)]:\n",
    "                if 0 <= r+i < len(grid) and 0 <= c+j < len(grid[0]) and grid[r+i][c+j] == 1:\n",
    "                    find_next(r+i, c+j, idx)\n",
    "\n",
    "        hashed_cache = set()\n",
    "        def add_hash(idx):\n",
    "            sig = []\n",
    "            for i, j in [(1,1), (1,-1), (-1,1), (-1,-1)]:\n",
    "                for s in (True, False):\n",
    "                    mnx, mny = inf, inf\n",
    "                    sig = []\n",
    "                    for p in islands[idx]:\n",
    "                        mnx = min(mnx, p[0]*i if s else p[1]*i)\n",
    "                        mny = min(mny, p[1]*j if s else p[0]*j)\n",
    "                    for p in islands[idx]:\n",
    "                        sig.append(((p[0]*i if s else p[1]*i) - mnx, (p[1]*j if s else p[0]*j) - mny))\n",
    "                    sig.sort()\n",
    "                    if tuple(sig) in hashed_cache:\n",
    "                        return  \n",
    "            hashed_cache.add(tuple(sig))\n",
    "        \n",
    "\n",
    "        for r in range(len(grid)):\n",
    "            for c in range(len(grid[0])):\n",
    "                if grid[r][c] == 1:\n",
    "                    islands.append([])\n",
    "                    find_next(r, c, len(islands)-1)\n",
    "        for i in range(len(islands)):\n",
    "            add_hash(i)\n",
    "        return len(hashed_cache)\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        islands = []\n",
    "        def find_next(r, c, idx):\n",
    "            grid[r][c] = 0\n",
    "            islands[idx].append((r,c))\n",
    "            for i, j in [(-1,0), (1,0), (0,-1), (0,1)]:\n",
    "                if 0 <= r+i < len(grid) and 0 <= c+j < len(grid[0]) and grid[r+i][c+j] == 1:\n",
    "                    find_next(r+i, c+j, idx)\n",
    "\n",
    "        hashed_cache = set()\n",
    "        def add_hash(idx):\n",
    "            sig = []\n",
    "            for i, j in [(1,1), (1,-1), (-1,1), (-1,-1)]:\n",
    "                for s in (True, False):\n",
    "                    mnx, mny = inf, inf\n",
    "                    sig = []\n",
    "                    for p in islands[idx]:\n",
    "                        mnx = min(mnx, p[0]*i if s else p[1]*i)\n",
    "                        mny = min(mny, p[1]*j if s else p[0]*j)\n",
    "                    for p in islands[idx]:\n",
    "                        sig.append(((p[0]*i if s else p[1]*i) - mnx, (p[1]*j if s else p[0]*j) - mny))\n",
    "                    sig.sort()\n",
    "                    if tuple(sig) in hashed_cache:\n",
    "                        return  \n",
    "            hashed_cache.add(tuple(sig))\n",
    "        \n",
    "\n",
    "        for r in range(len(grid)):\n",
    "            for c in range(len(grid[0])):\n",
    "                if grid[r][c] == 1:\n",
    "                    islands.append([])\n",
    "                    find_next(r, c, len(islands)-1)\n",
    "        for i in range(len(islands)):\n",
    "            add_hash(i)\n",
    "        return len(hashed_cache)\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # DFS + Canonical Serialization. Time O(mnlog(mn)) Space O(mn)\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        res = set()\n",
    "        def dfs(x, y):\n",
    "            if grid[x][y] == 0: return\n",
    "            self.island.append((x, y))\n",
    "            grid[x][y] = 0\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        # get the canonical serialization of an island\n",
    "        def canonical(island):\n",
    "            # 8 operations allowed:\n",
    "            # (x, y), (-x, y), (x, -y), (-x, -y), (y, x)         , (-y, x), (y, -x), (-y, -x)\n",
    "            # start , ver ref, hor ref, ro 180  , ro 90 & ver ref, ro 270 , ro 90  , ro 270 & ver ref\n",
    "            ops = [(1, 1), (-1, 1), (1, -1), (-1, -1)]\n",
    "            # get all 8 variants of the island\n",
    "            variants = [[] for _ in range(8)]\n",
    "            for i, (opx, opy) in enumerate(ops):\n",
    "                for x, y in island:\n",
    "                    variants[i].append([opx * x, opy * y])\n",
    "                    variants[i+4].append([opx * y, opy * x])\n",
    "            # change the land indices to the relative distance to minx and miny\n",
    "            # imagine use a smallest rectangle to wrap the island, upper-left corner is (minx, miny)\n",
    "            # sort each variant as well\n",
    "            for variant in variants:\n",
    "                minx, miny = min([x for x, _ in variant]), min([y for _, y in variant])\n",
    "                for pos in variant:\n",
    "                    pos[0], pos[1] = pos[0] - minx, pos[1] - miny\n",
    "                variant.sort()\n",
    "            # build the list(list) into tuple(tuple)\n",
    "            return tuple([tuple(pos) for pos in max(variants)])\n",
    "\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 1:\n",
    "                    self.island = []\n",
    "                    dfs(x, y)\n",
    "                    res.add(canonical(self.island))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        res = set()\n",
    "        def dfs(x, y):\n",
    "            if grid[x][y] == 0: return\n",
    "            self.island.append((x, y))\n",
    "            grid[x][y] = 0\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        def canonical(island):\n",
    "            ops = [(1, 1), (-1, 1), (1, -1), (-1, -1)]\n",
    "            variants = [[] for _ in range(8)]\n",
    "            for i, (opx, opy) in enumerate(ops):\n",
    "                for x, y in island:\n",
    "                    variants[i].append([opx * x, opy * y])\n",
    "                    variants[i+4].append([opx * y, opy * x])\n",
    "            for variant in variants:\n",
    "                minx, miny = min([x for x, _ in variant]), min([y for _, y in variant])\n",
    "                for pos in variant:\n",
    "                    pos[0], pos[1] = pos[0] - minx, pos[1] - miny\n",
    "                variant.sort()\n",
    "            return tuple([tuple(pos) for pos in max(variants)])\n",
    "\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 1:\n",
    "                    self.island = []\n",
    "                    dfs(x, y)\n",
    "                    res.add(canonical(self.island))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # DFS + Canonical Serialization. Time O(mnlog(mn)) Space O(mn)\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        res = set()\n",
    "        def dfs(x, y):\n",
    "            if grid[x][y] == 0: return\n",
    "            self.island.append((x, y))\n",
    "            grid[x][y] = 0\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        # get the canonical serialization of an island\n",
    "        def canonical(island):\n",
    "            # 8 operations allowed:\n",
    "            # (x, y), (-x, y), (x, -y), (-x, -y), (y, x)         , (-y, x), (y, -x), (-y, -x)\n",
    "            # start , ver ref, hor ref, ro 180  , ro 90 & ver ref, ro 270 , ro 90  , ro 270 & ver ref\n",
    "            ops = [(1, 1), (-1, 1), (1, -1), (-1, -1)]\n",
    "            # get all 8 variants of the island\n",
    "            variants = [[] for _ in range(8)]\n",
    "            for i, (opx, opy) in enumerate(ops):\n",
    "                for x, y in island:\n",
    "                    variants[i].append([opx * x, opy * y])\n",
    "                    variants[i+4].append([opx * y, opy * x])\n",
    "            # change the land indices to the relative distance to minx and miny\n",
    "            # imagine use a smallest rectangle to wrap the island, upper-left corner is (minx, miny)\n",
    "            # sort each variant as well\n",
    "            for variant in variants:\n",
    "                minx, miny = min([x for x, _ in variant]), min([y for _, y in variant])\n",
    "                for pos in variant:\n",
    "                    pos[0], pos[1] = pos[0] - minx, pos[1] - miny\n",
    "                variant.sort()\n",
    "            # take the max of variants and build the list(list) into tuple(tuple)\n",
    "            return tuple([tuple(pos) for pos in max(variants)])\n",
    "\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 1:\n",
    "                    self.island = []\n",
    "                    dfs(x, y)\n",
    "                    res.add(canonical(self.island))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0]) \n",
    "        vis = [[0] * n for _ in range(m)]\n",
    "        def dfs(i,j, ans):\n",
    "            vis[i][j] = 1\n",
    "            ans.append((i,j))\n",
    "            for ni,nj in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:\n",
    "                if 0<=ni<m and 0<=nj<n and grid[ni][nj] ==1 and not vis[ni][nj]:\n",
    "                    dfs(ni,nj, ans)\n",
    "        def func(ans):\n",
    "            x1, y1, x2, y2 = m,n,0,0\n",
    "            for x,y in ans:\n",
    "                x1 = min(x1,x)\n",
    "                x2 = max(x2,x)\n",
    "                y1 = min(y1,y)\n",
    "                y2 = max(y2,y) \n",
    "            vec1 = [0] * (x2-x1+1) \n",
    "            vec2 = [0] * (y2-y1+1)\n",
    "            l1, l2 = len(vec1),len(vec2) \n",
    "            diag1 = [0] * (l1 + l2 - 1)\n",
    "            diag2 = [0] * (l1 + l2 - 1)\n",
    "            for x, y in ans:\n",
    "                vec1[x-x1] += 1\n",
    "                vec2[y-y1] += 1\n",
    "                diag1[(x-x1) + (y-y1)] += 1 \n",
    "                diag2[(x-x1) - (y-y1) + l2 - 1] += 1\n",
    "            return tuple(vec1), tuple(vec2), tuple(diag1), tuple(diag2) \n",
    "\n",
    "        arr = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and not vis[i][j]:\n",
    "                    ans = [] \n",
    "                    dfs(i,j, ans) \n",
    "                    row,col,diag1,diag2 = func(ans) \n",
    "                    arr.append((row, col, diag1, diag2)) \n",
    "        l = len(arr)\n",
    "        #print(arr) \n",
    "        def eq(a,b):\n",
    "            return (a == b) or (a == b[::-1])\n",
    "        f = defaultdict(int)  \n",
    "        cnt = 0\n",
    "        for i in range(l):\n",
    "            if arr[i] in f:\n",
    "                continue \n",
    "            cnt += 1\n",
    "            f[arr[i]] = cnt \n",
    "            a1,b1,c1,d1 = arr[i]\n",
    "            for j in range(i+1,l):\n",
    "                if arr[j] not in f:\n",
    "                    a2,b2,c2,d2 = arr[j] \n",
    "                    if (eq(a1,a2) and eq(b1,b2) or eq(a1,b2) and eq(b1,a2)) and \\\n",
    "                    (eq(c1,c2) and eq(d1,d2) or eq(c1,d2) and eq(d1,c2)): \n",
    "                        f[arr[j]] = cnt \n",
    "                        #print(cnt) \n",
    "        return cnt \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        res = set()\n",
    "        def dfs(x, y):\n",
    "            if grid[x][y] == 0: return\n",
    "            self.island.append((x, y))\n",
    "            grid[x][y] = 0\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        def canonical(island):\n",
    "            ops = [(1, 1), (-1, 1), (1, -1), (-1, -1)]\n",
    "            variants = [[] for _ in range(8)]\n",
    "            for i, (opx, opy) in enumerate(ops):\n",
    "                for x, y in island:\n",
    "                    variants[i].append([opx * x, opy * y])\n",
    "                    variants[i+4].append([opx * y, opy * x])\n",
    "            for variant in variants:\n",
    "                minx, miny = min([x for x, _ in variant]), min([y for _, y in variant])\n",
    "                for pos in variant:\n",
    "                    pos[0], pos[1] = pos[0] - minx, pos[1] - miny\n",
    "                variant.sort()\n",
    "            return tuple([tuple(pos) for pos in max(variants)])\n",
    "\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 1:\n",
    "                    self.island = []\n",
    "                    dfs(x, y)\n",
    "                    res.add(canonical(self.island))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def normalize(island):\n",
    "            # Create 8 lists to represent the 8 possible transformations: \n",
    "            # 4 for rotation and 4 for reflection.\n",
    "            ways = [[] for _ in range(8)]\n",
    "            for i, j in island:\n",
    "                ways[0].append((i, j))\n",
    "                ways[1].append((i, -j))\n",
    "                ways[2].append((-i, j))\n",
    "                ways[3].append((-i, -j))\n",
    "                ways[4].append((j, i))\n",
    "                ways[5].append((j, -i))\n",
    "                ways[6].append((-j, i))\n",
    "                ways[7].append((-j, -i))\n",
    "            # Sort the coordinates in each transformation.\n",
    "            ways = [sorted(w) for w in ways]\n",
    "            # Normalize each transformation by adjusting its coordinates relative to the first coordinate.\n",
    "            for w in ways:\n",
    "                ref = w[0]\n",
    "                for i in range(len(island)):\n",
    "                    w[i] = (w[i][0] - ref[0], w[i][1] - ref[1])\n",
    "            # Return the lexicographically smallest representation among the 8 transformations.\n",
    "            return tuple(sorted(ways)[0])\n",
    "       \n",
    "        def dfs(i, j):\n",
    "            island.append((i, j))\n",
    "            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):\n",
    "                x, y = i + dx, j + dy\n",
    "                if 0 <= x < m and 0 <= y < n and (x, y) not in visit and grid[x][y]==1:\n",
    "                    visit.add((x, y))\n",
    "                    dfs(x, y)\n",
    "\n",
    "        visit = set()\n",
    "        islands = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 or (i, j) in visit:\n",
    "                    continue\n",
    "                island = []\n",
    "                visit.add((i, j))\n",
    "                dfs(i, j)\n",
    "                if island:\n",
    "                    islands.add(normalize(island))\n",
    "        return len(islands)\n",
    "\"\"\"\n",
    "把岛屿坐标,放到坐标系上,然后画一下,求形状, 就是 求坐标间的相对位置. 坐标间相对位置(值)一样,形状就一样.\n",
    "\n",
    "上下翻转:  x 坐标不变, y 坐标取反. (x, y) --> (x, -y)\n",
    "左右翻转: x 坐标取反, y 坐标不变.  (x, y) --> (-x, y)\n",
    "旋转90°:  (x, y) --> (y, -x)\n",
    "旋转180°, 270°:  就是在 旋转90° 后,在旋转1次, 2次.\n",
    "一共8个方向, 然后排序,减去每个岛屿坐标集的里最小值. 就可得其相对自身最小坐标的形状.\n",
    "set() / dict() 去重,就是个数.\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDistinctIslands2(self, grid: List[List[int]]) -> int:\n",
    "        seen = set()\n",
    "        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))\n",
    "\n",
    "        def dfs(x, y):\n",
    "            island.append((x, y))\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and (nx, ny) not in seen and grid[nx][ny]==1:\n",
    "                    seen.add((nx, ny))\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        # Define a function to normalize the coordinates of an island.\n",
    "        # This function ensures that the shape of an island is represented in a unique way, regardless of rotation or reflection.\n",
    "        def normalize(island):\n",
    "            # Create 8 lists to represent the 8 possible transformations: \n",
    "            # 4 for rotation and 4 for reflection.\n",
    "            ways = [[] for _ in range(8)]\n",
    "            for i, j in island:\n",
    "                ways[0].append((i, j))\n",
    "                ways[1].append((i, -j))\n",
    "                ways[2].append((-i, j))\n",
    "                ways[3].append((-i, -j))\n",
    "                ways[4].append((j, i))\n",
    "                ways[5].append((j, -i))\n",
    "                ways[6].append((-j, i))\n",
    "                ways[7].append((-j, -i))\n",
    "            # Sort the coordinates in each transformation.\n",
    "            ways = [sorted(w) for w in ways]\n",
    "            # Normalize each transformation by adjusting its coordinates relative to the first coordinate.\n",
    "            for w in ways:\n",
    "                ref = w[0]\n",
    "                for i in range(len(island)):\n",
    "                    w[i] = (w[i][0] - ref[0], w[i][1] - ref[1])\n",
    "            # Return the lexicographically smallest representation among the 8 transformations.\n",
    "            return tuple(sorted(ways)[0])\n",
    "\n",
    "        islands = set()\n",
    "        for x in range(len(grid)):\n",
    "            for y in range(len(grid[0])):\n",
    "                if grid[x][y] == 0 or (x, y) in seen:\n",
    "                    continue\n",
    "                island = []\n",
    "                seen.add((x, y))\n",
    "                dfs(x, y)\n",
    "                if island:\n",
    "                    islands.add(normalize(island))\n",
    "        return len(islands)\n",
    "\"\"\"\n",
    "把岛屿坐标,放到坐标系上,然后画一下,求形状, 就是 求坐标间的相对位置. 坐标间相对位置(值)一样,形状就一样.\n",
    "\n",
    "上下翻转:  x 坐标不变, y 坐标取反. (x, y) --> (x, -y)\n",
    "左右翻转: x 坐标取反, y 坐标不变.  (x, y) --> (-x, y)\n",
    "旋转90°:  (x, y) --> (y, -x)\n",
    "旋转180°, 270°:  就是在 旋转90° 后,在旋转1次, 2次.\n",
    "一共8个方向, 然后排序,减去每个岛屿坐标集的里最小值. 就可得其相对自身最小坐标的形状.\n",
    "set() / dict() 去重,就是个数.\n",
    "\"\"\""
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
